package leetcode.top100;


import utils.TreeNode;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

/**
 * 反转二叉树
 * 输入：
 * <p>
 *   4
 * /   \
 * 2     7
 * / \   / \
 * 1   3 6   9
 * 输出：
 * <p>
 *   4
 * /   \
 * 7     2
 * / \   / \
 * 9   6 3   1
 *
 * 考察的就是各种遍历，在遍历的时候 ，对节点进行左右孩子引用互换
 * @since 2019/12/17 0017 上午 10:16
 */
public class Code226_ReverseBT {
    public TreeNode invertTree(TreeNode root) {
        if(root == null) return root;
        TreeNode temp = root;
        process2(root);
        return temp;
    }

    //in order recursion
    public static void process1(TreeNode root){
        if(root == null) return;
        //change left and right for each node
        TreeNode temp = root.left;
        root.left = root.right;
        root.right = temp;
        //no mater visited who first
        process1(root.right);
        process1(root.left);
    }
    // in order iterator
    public static void process2(TreeNode root){
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        while(!stack.isEmpty()){
            root = stack.pop();
            //change the link
            TreeNode temp = root.left;
            root.left = root.right;
            root.right = temp;
            //reverse in order
            if(root.left != null){
                stack.push(root.left);
            }
            if(root.right != null){
                stack.push(root.right);
            }
        }
    }
    // level traverse
    public static void process3(TreeNode root){
        Queue<TreeNode> quque = new LinkedList<>();
        quque.add(root);
        while(!quque.isEmpty()){
            root = quque.poll();
            //change the  node
            TreeNode temp = root.left;
            root.left = root.right;
            root.right = temp;
            if(root.right != null){
                quque.add(root.right);
            }
            if(root.left != null){
                quque.add(root.left);
            }
        }

    }



}
